package likouJava;

import java.util.HashMap;
import java.util.Map;

public class 实现Trie前缀树 {

    // 定义 Trie 节点
    class TrieNode {
        boolean isWord; // 标记是否是一个完整单词的结尾
        Map<Character, TrieNode> children;

        TrieNode() {
            isWord = false;
            children = new HashMap<>();
        }
    }

    private TrieNode root;

    public void Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()){
            //如果没有就创建这个字符,创建一个子节点
            node.children.putIfAbsent(c, new TrieNode());
            //移动到下一个
            node = node.children.get(c);
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()){
            if (!node.children.containsKey(c)){
                return false;   //没有找到对应字符
            }
            node = node.children.get(c);
        }
        return node.isWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()){
            if (!node.children.containsKey(c)){
                return false;
            }
            node = node.children.get(c);
        }
        return true;
    }

}
